package search

/**
二分查找的变形版本
1.从给定序列中查找第一个匹配元素
2.从给定序列中查找最后一个匹配元素
3.在给定序列中查找第一个大于等于给定值的元素
4.在给定序列中查找最后一个小于等于给定值的元素
*/

/**
二分查找变形版本1：查找第一个值等于给定值的元素

在序列中找到值等于待查找元素值时，如果此时 mid 位置已经到了序列的最左边，不能再往左了，
或者序列中索引小于 mid 的上一个元素值不等于待查找元素值，那么此时 mid 就是第一个等于待查找元素值的位置；否则还要继续往前找。
*/
func BinarySearchV1(nums []int, num int) int {
	return binarySearchV1(nums, num, 0, len(nums)-1)
}
func binarySearchV1(nums []int, num, low, high int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if num < nums[mid] {
		return binarySearchV1(nums, num, low, mid-1)
	} else if num > nums[mid] {
		return binarySearchV1(nums, num, mid+1, high)
	} else {
		// 除了需要判断第一个与 num 相等的元素索引外，其他和普通二分查找逻辑一致
		if mid == 0 || nums[mid-1] != num {
			return mid
		} else {
			return binarySearchV1(nums, num, low, mid-1)
		}
	}
}

// 二分查找变形版本2：查找最后一个值等于给定值的元素
func BinarySearchV2(nums []int, num int) int {
	return binarySearchV2(nums, num, 0, len(nums)-1)
}
func binarySearchV2(nums []int, num, low, high int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if num < nums[mid] {
		return binarySearchV2(nums, num, low, mid-1)
	} else if num > nums[mid] {
		return binarySearchV2(nums, num, mid+1, high)
	} else {
		// 除了需要判断最后一个与 num 相等的元素索引外，其他和普通二分查找逻辑一致
		if mid == len(nums)-1 || nums[mid+1] != num {
			return mid
		} else {
			return binarySearchV2(nums, num, mid+1, high)
		}
	}
}

// 二分查找变形版本3：查找第一个大于等于给定值的元素
func BinarySearchV3(nums []int, num int) int {
	return binarySearchV3(nums, num, 0, len(nums)-1)
}
func binarySearchV3(nums []int, num, low, high int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if num <= nums[mid] {
		// 判断条件变更，找到第一个大于等于给定值的元素
		// 最左侧元素值，或者当前 mid 位置前一个元素值小于给定值
		if mid == 0 || nums[mid-1] < num {
			return mid
		} else {
			return binarySearchV3(nums, num, low, mid-1)
		}
	} else {
		return binarySearchV3(nums, num, mid+1, high)
	}
}

// 二分查找变形版本4：查找最后一个小于等于给定值的元素
func BinarySearchV4(nums []int, num int) int {
	return binarySearchV4(nums, num, 0, len(nums)-1)
}
func binarySearchV4(nums []int, num, low, high int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if num >= nums[mid] {
		// 判断条件变更，找到最后一个小于等于给定值的元素
		// 最右侧元素值，或者当前 mid 位置后一个元素值大于给定值
		if mid == len(nums)-1 || nums[mid+1] > num {
			return mid
		} else {
			return binarySearchV4(nums, num, mid+1, high)
		}
	} else {
		return binarySearchV4(nums, num, low, mid-1)
	}
}
